/*
 * 线性表-顺序存储结构
 */

#include <stdio.h>
#include <string.h>


#define LISTSIZE 100


/* type */
struct Student {
    int id;
    char name[100];
    int age;
    char sex;
};
typedef struct Student ElemType;
//typedef int ElemType;


/*
 *
 */
struct seq_list {
    ElemType data[LISTSIZE];    /* number of elements can store */
    int length;                 /* current length of list */
};
typedef struct seq_list seq_list_t;


void init_seq_list(seq_list_t *list);
int seq_list_length(seq_list_t *list);
void free_seq_list(seq_list_t *list);
int get_seq_list(seq_list_t *list, int pos, ElemType *item);
int insert_seq_list(seq_list_t *list, int pos, ElemType *item);
int delete_seq_list(seq_list_t *list, int pos, ElemType *item);
int find_seq_list(seq_list_t *list, ElemType *item);





int
main(int argc, char *argv[])
{
    seq_list_t list;
    int i, n;
    ElemType item;

    init_seq_list(&list);
    printf("seq length = %d\n", seq_list_length(&list));

    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        insert_seq_list(&list, i+1, &item);
    }



    /* 在第5个位置插入一个节点 (新插入节点排在第5位) */
    memset(&item, 0, sizeof(item));
    item.id = 11;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 5, &item);

    /* 在最后1个位置后插入一个节点 (新插入节点排在第12位) */
    memset(&item, 0, sizeof(item));
    item.id = 12;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    n = seq_list_length(&list);
    insert_seq_list(&list, n+1, &item);


    memset(&item, 0, sizeof(item));
    item.id = 13;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 1, &item);

    memset(&item, 0, sizeof(item));
    item.id = 14;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 1, &item);



    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_seq_list(&list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_seq_list(&list, -1, &item));




    printf("\n");
    n = seq_list_length(&list);
    printf("After insert: n=[%d]\n", n);
    for (i = 0; i < list.length; ++i) {
        memset(&item, 0, sizeof(item));
        get_seq_list(&list, i+1, &item);
        printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", i+1, item.id, item.name);
    }
    printf("seq length = %d\n", seq_list_length(&list));





    /* 删除第一个元素 */
    delete_seq_list(&list, 1, &item);

    /* 删除最后一个元素 */
    n = seq_list_length(&list);
    delete_seq_list(&list, n, &item);

    /* 删除第3个元素 */
    memset(&item, 0, sizeof(item));
    delete_seq_list(&list, 3, &item);
    printf("\n");
    printf("Delete list pos=3, Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);

    /* 删除第一个元素 */
    delete_seq_list(&list, 1, &item);

    /* 删除最后一个元素 */
    n = seq_list_length(&list);
    delete_seq_list(&list, n, &item);



    printf("\n");
    n = seq_list_length(&list);
    printf("After insert: n=[%d]\n", n);
    for (i = 0; i < list.length; ++i) {
        memset(&item, 0, sizeof(item));
        get_seq_list(&list, i+1, &item);
        printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", i+1, item.id, item.name);
    }
    printf("seq length = %d\n", seq_list_length(&list));






    /* 查找元素 */
    printf("\n");
    memset(&item, 0, sizeof(item));
    item.id = 7;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_seq_list(&list, &item))
        printf("元素[%d]能找到, Stud_Name[%s], pos[%d]\n", item.id, item.name, n);
    else
        printf("元素[%d]不能找到\n", item.id);

    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_seq_list(&list, &item))
        printf("元素[%d]能找到, Stud_Name[%s], pos[%d]\n", item.id, item.name, n);
    else
        printf("元素[%d]不能找到\n", item.id);




    printf("\n");
    printf("删除链表前，元素个数[%d]\n", seq_list_length(&list));
    free_seq_list(&list);
    free_seq_list(&list);
    printf("After free list, length = %d\n", seq_list_length(&list));




    init_seq_list(&list);
    printf("seq length = %d\n", seq_list_length(&list));



    /* 空链表插入第一个节点 */
    memset(&item, 0, sizeof(item));
    item.id = 1;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 2;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 3;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 1, &item);

    /* 在第2个位置插入一个节点 (新插入节点排在第2位) */
    memset(&item, 0, sizeof(item));
    item.id = 4;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_seq_list(&list, 2, &item);


    printf("\n");
    printf("After insert: n=[%d]\n", seq_list_length(&list));
    for (i = 0; i < list.length; ++i) {
        memset(&item, 0, sizeof(item));
        get_seq_list(&list, i+1, &item);
        printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", i+1, item.id, item.name);
    }
    printf("seq length = %d\n", seq_list_length(&list));




    printf("\n");
    printf("删除链表前，元素个数[%d]\n", seq_list_length(&list));
    free_seq_list(&list);
    printf("After free list, length = %d\n", seq_list_length(&list));



    return 0;
}



/******************************************************************************/



/*
 * 可以考虑为宏定义或inline函数
 * 或者直接自己初始化
 */
void
init_seq_list(seq_list_t *list)
{
    memset(list, 0, sizeof(seq_list_t));
}

/*
 * 返回线性表的个数
 * 可以自己直接读list->length
 */
int
seq_list_length(seq_list_t *list)
{
    return list->length;
}

/*
 * 清空线性表
 */
void
free_seq_list(seq_list_t *list)
{
    memset(list, 0, sizeof(seq_list_t));
}

/*
 * 将第i个位置的元素返回
 * pos的范围是 [1, length]
 * 不是从0开始哦！
 * 成功返回0
 *
 * 时间复杂度为 O(1)
 */
int
get_seq_list(seq_list_t *list, int pos, ElemType *item)
{
    if (list->length == 0 || pos < 1 || pos > list->length)
        return -1;
    if (item == NULL)
        return -2;

    /* 注意要 pos-1 */
    *item = list->data[pos-1];

    return 0;
}

/*
 * 插入算法的思路;
 * 1. 如果插入位置不合理，抛出异常;
 * 2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;
 * 3. 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置;
 * 4. 将要插入元素填入位置 i 处;
 * 5. 表长加1。
 *
 * pos:     1 2 3 4 5
 * data:    x x x x x
 * index:   0 1 2 3 4 5 6
 * length = 5
 * pos的范围是 [1, length+1]
 *
 * 返回插入元素后表的长度
 *
 * 时间复杂度为 O(n)
 */
int
insert_seq_list(seq_list_t *list, int pos, ElemType *item)
{
    int i;

    /* list is full */
    if (list->length >= LISTSIZE)
        return -1;

    /* position is wrong, [1, length+1] */
    if (pos < 1 || pos > (list->length + 1))
        return -2;

    /* if not insert at tail */
    if (pos <= list->length) {
        /* 从插入位置的数据开始，往后移 */
        for (i = list->length - 1; i >= pos - 1; --i)
            list->data[i+1] = list->data[i];
    }
    memset(&list->data[pos-1], 0, sizeof(ElemType));
    list->data[pos-1] = *item;

    return ++(list->length);
}

/*
 * 删除算法的思路:
 * 1. 如果删除位置不合理，抛出异常；
 * 2. 取出删除元素;
 * 3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置;
 * 4. 表长减1。
 *
 * pos:     1 2 3 4 5
 * data:    x x x x x
 * index:   0 1 2 3 4 5 6
 * length = 5
 * pos的范围是 [1, length]
 *
 * 返回删除元素后表的长度
 *
 * 时间复杂度为 O(n)
 */
int
delete_seq_list(seq_list_t *list, int pos, ElemType *item)
{
    int i;

    /* list is empty */
    if (list->length == 0)
        return 0;

    /* position is wrong, [1, length] */
    if (pos < 1 || pos > list->length)
        return -1;

    if (item != NULL)
        *item = list->data[pos-1];

    /* if not delete at tail */
    if (pos < list->length) {
        /* 从删除位置的数据后一位开始，往前移 */
        for (i = pos; i < list->length; ++i)
            list->data[i-1] = list->data[i];
    }
    /* 原来的最后一位清空 */
    memset(&list->data[list->length - 1], 0, sizeof(ElemType));

    return --(list->length);
}

/*
 * 查找元素在表中的位置
 * 返回的位置为[1, length]，若找不到返回0
 *
 * 时间复杂度为 O(n)
 */
int
find_seq_list(seq_list_t *list, ElemType *item)
{
    int i;
    for (i = 0; i < list->length; ++i) {
        if (memcmp(&list->data[i], item, sizeof(ElemType)) == 0)
            return i+1;
    }

    return 0;
}

